//题目:
//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
// 此外，你可以假设该网格的四条边均被水包围。
#include<iostream>
#include<vector>
#include<set>

using namespace std;
//代码:
class Solution 
{
public:
    int numIslands(vector<vector<char>>& grid) 
    {
        // int arr_x[]={-1,1,0,0},arr_y[]={0,0,-1,1};
        // int ret=0;
        // for(int i=0;i<grid.size();i++)
        // {
        //     for(int j=0;j<grid[i].size();j++)
        //     {
        //         if(grid[i][j]=='1')
        //         {
        //             ret++;
        //             queue<pair<int,int>> q;//pair内存放的是岛的坐标
        //             q.push(make_pair(i,j));
        //             grid[i][j]='0';
        //             while(!q.empty())
        //             {
        //                 pair<int,int> pir=q.front();
        //                 q.pop();
        //                 //将上下左右相邻岛屿入队列
        //                 for(int k=0;k<4;k++)
        //                 {
        //                     int x=pir.first+arr_x[k],y=pir.second+arr_y[k];
        //                     if(x>=0 && x<grid.size() && y>=0 && y<grid[0].size() && grid[x][y]=='1')
        //                     {
        //                         q.push(make_pair(x,y));
        //                         grid[x][y]='0';
        //                     }
        //                 }
        //             }
        //         }
        //     }
        // }
        // return ret;

        int ret=0;
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[i].size();j++)
            {
                if(grid[i][j]=='1')
                {
                    dfs(grid,i,j);
                    ret++;
                }
            }
        }

        return ret;
    }

    int arr_x[4]={-1,1,0,0},arr_y[4]={0,0,-1,1};
    void dfs(vector<vector<char>>& grid,int row,int col)
    {
        grid[row][col]='0';

        //判断(row,col)相邻位置是否存在陆地
        for(int i=0;i<4;i++)
        {
            int x=row+arr_x[i], y=col+arr_y[i];
            if(x>=0 && x<grid.size() && y>=0 && y<grid[0].size() && grid[x][y]=='1')
            {
                dfs(grid,x,y);
            }
        }
    }
};